<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /* 
            示例 1:
                示例 1：

                输入：nums = [1,2,3], target = 4
                输出：7
                解释：
                所有可能的组合为：
                (1, 1, 1, 1)
                (1, 1, 2)
                (1, 2, 1)
                (1, 3)
                (2, 1, 1)
                (2, 2)
                (3, 1)
                请注意，顺序不同的序列被视作不同的组合。
                示例 2：

                输入：nums = [9], target = 3
                输出：0
        */


        /*
            动态规划解法:
            这个解法好理解
            类型：完全背包问题（每个数组可以取任意多个），排列问题

            dp含义：dp[i][j] => 从0-i个数字里面，取，放满背包j的组合数
            递推公式:
                dp[i][j] = dp[i - 1][j] + dp[i][j - nums[i]]
            初始化：
                dp[i][0]必须是1
                dp[0][j]必须是1
            遍历顺序：
                先遍历背包，
                再遍历物品，物品正序开始遍历
        */
        var combinationSum4 = function(nums, target) {
            let dp = new Array(target + 1).fill(0)
            // 第一个数必须为0
            dp[0] = 1
            // j为什么可以从0开始，因为j-nums[i]必须大于0，才能进入递推公式
            for (let j = 0; j <= target; j++) {
                // i为什么从0开始，必须每个物品都考虑在里面
                for (let i = 0; i < nums.length; i++) {
                    // 未加判断条件，得出的是NaN，会访问dp[-1]
                    if (dp[j - nums[i]] > 0) {
                        dp[j] = dp[j] + dp[j - nums[i]]
                    }
                }
            }
            return dp[target]
        };
        console.log(combinationSum4([1, 2, 3], 4));
    </script>
</body>

</html>